234 回文链表

https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnv1oc/

https://leetcode.cn/problems/palindrome-linked-list/description/

cost: 8m17s

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        this->head = head;
        return this->isPalindrome_(head);
    }

private:
    bool isPalindrome_(ListNode* node) {
        if (node == nullptr) {
            return true;
        }
        if (node->next == nullptr) {
            bool r = this->head->val == node->val;
            this->head = this->head->next;
            return r;
        }
        bool r = this->isPalindrome_(node->next);
        r = r && (node->val == this->head->val);
        this->head = this->head->next;
        return r;
    }
    ListNode* head = nullptr;
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)